package leetcode_101_120;

import java.util.ArrayList;
import java.util.List;

public class generate_118 {
    /**
     * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
     *
     * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     */
    public List<List<Integer>> generate(int numRows) {
        /**
         * 思路很简单
         * 第n排的数字
         * 为 0， a[ n-1 ][ 0 ] ，a[ n-1 ][ 1 ] ，... ，a[ n-1 ][ n-1 ] ，0 这些相邻数字的两两之和的集合
         * 1ms
         * 15分钟解决
         */
        List<List<Integer>>ans=new ArrayList<>();
        List<Integer>list=new ArrayList<>();
        list.add(1);
        ans.add(list);
        for(int i=1;i<numRows;i++){
            List<Integer>l=new ArrayList<>();
            l.add(1);        //这一步等于0+a[ n-1 ][ 0 ],也就是1
            int a=1,b;
            for (int t=0;t < ans.get(i-1).size()-1;t++){
                b=ans.get(i - 1).get(t+1); //后一个元素
                l.add(a+b);  //相邻数字之和
                a=b;  //将下一次使用的b赋值给a
            }
            l.add(1);        //这一步等于a[ n-1 ][ n-1 ] + 0,也就是1
            ans.add(l);
        }
        return ans;
    }



    public List<Integer> getRow(int rowIndex) {
        /**
         * 和上一题没有太大区别
         */
        List<Integer>list=new ArrayList<>();
        list.add(1);
        for(int i=1;i<rowIndex+1;i++){
            List<Integer>l=new ArrayList<>();
            l.add(1);        //这一步等于0+a[ n-1 ][ 0 ],也就是1
            int a=1,b;
            for (int t=0;t < list.size()-1;t++){
                b=list.get(t+1); //后一个元素
                l.add(a+b);  //相邻数字之和
                a=b;  //将下一次使用的b赋值给a
            }
            l.add(1);        //这一步等于a[ n-1 ][ n-1 ] + 0,也就是1
            list=l;
        }
        return list;
    }
}
